02｜前缀和（1D/2D）（知识笔记）

对应课程：lessons/02-prefix-diff-two-pointers/00-prefix-sum-1d-2d.md

识别信号

• 多次区间和/区间计数
• 子矩阵和/矩形统计
• 需要把区间约束变成“两个前缀的差”

一维前缀和

• 定义：pre[i] = a[1] + ... + a[i]，并约定 pre[0]=0
• 区间和：sum(l,r) = pre[r] - pre[l-1]

高频变形：

• 前缀和 + 频率表：统计满足某条件的子数组数量（例如 pre[j]-pre[i]=k）
• 前缀最值：把“最优子段”转化成前缀差

二维前缀和

• 定义：pre[i][j] 表示从 (1,1) 到 (i,j) 的矩形和
• 子矩形和（容斥）：
  • S(x1,y1,x2,y2) = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]

常见坑（非常高频）

• 下标：强烈建议 1-index，并给 0 行/0 列当缓冲
• 溢出：二维和/计数几乎必用 long long
• 容斥符号写错：最后一项必须是 +

自检

• [ ] 手算一个 2x2 的子矩形验证容斥
• [ ] 边界 x1=1 或 y1=1 时是否正确

个人坑位

• （例）我经常把 pre[x1-1][y1-1] 写错成 pre[x1][y1]